package com.linzm.leetcode.mid.tree.层次遍历;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author zimingl
 * @Date 2023/2/20 23:40
 * @Description: 给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
 * 树中节点数量在 [1, 104] 范围内
 * -231 <= Node.val <= 231 - 1
 */
public class AverageOfLevels637 {
    public static void main(String[] args) {
        AverageOfLevels637 averageOfLevels637 = new AverageOfLevels637();
        List<Double> doubles = averageOfLevels637.averageOfLevels(TreeNode.getTree());
        System.out.println(doubles);
    }

    public List<Double> averageOfLevels(TreeNode root) {
        if (root == null) return new ArrayList<>();
        List<Double> res = new ArrayList<>();
        Deque<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            long sum = 0;
            int len = queue.size();
            int count = queue.size();
            while (len > 0) {
                root = queue.poll();
                sum += root.val;
                if (root.left != null) queue.offer(root.left);
                if (root.right != null) queue.offer(root.right);
                len--;
            }
            res.add((double) sum / count);
        }
        return res;
    }
}
